/*P2764 最小路径覆盖问题
 *题目描述
 *给定有向图G=(V,E)。设P是G的一个简单路(顶点不相交)的集合。如果V中每个定点恰好在P的一条路上，则称P是G的一个路径覆盖。P中路径可以从V的任何一个定点开始，长度也是任意的，特别地，可以为0。G的最小路径覆盖是G所含路径条数最少的路径覆盖。设计一个有效算法求一个DAG(有向无环图)G的最小路径覆盖。
 *解题思路
 *初始状态下，每个顶点就是一条路径，然后，有原始边的点可以合并成一条路径，显然，要尽量合并，那么就是一个最大匹配问题。
 *当然，要拆点才能得到二分集。
 *在拆出来的二分图中，镜像点如果有流入，说明它在路径上的另一个点之后，不可能是路径的起点，如果找到没有流入的（从建图过程来看，有的点可能连入边都没有，所以应该判断到超级汇点还有没有残余流量）
 *然后就按照匹配的顺序依次输出，直到没有匹配为止，然后再找下一条路径。
*/
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;
class flowedge{
    int m_v;
    int m_w;
    int m_cost;
    int m_capacity;
    int m_flow=0;
    public:
    void set(int v,int w,int capacity,int cost=0){
        m_v=v;
        m_w=w;
        m_capacity=capacity;
        m_cost=cost;//板子带来的，此题没用
    }
    int from(){return m_v;}
    int to(){return m_w;}
    int other(int vertex){
        if(vertex==m_v)
            return m_w;
        else if(vertex==m_w)
            return m_v;
        else
            throw "vertex is error!";
    }
    int flow(){return m_flow;}
    int costTo(int vertex){
        if(vertex==m_v)
            return -m_cost;
        else if(vertex==m_w)
            return m_cost;
        else
            throw "vertex is error!";
    }
    int residualCapacityTo(int vertex){
        if(vertex==m_v)
            return m_flow;
        else if(vertex==m_w)
            return m_capacity-m_flow;
        else
            throw "vertex is error!";
    }
    void addResidualFlowTo(int vertex,int delta){
        if(vertex==m_v)
            m_flow-=delta;
        else if(vertex==m_w)
            m_flow+=delta;
        else
            throw "vertex is error!";
    } 
};
class flowgraph{
    int m_v;
    int m_e;
    int m_tail=0;
    flowedge *m_allEdge;
    vector<flowedge *> *m_adj;
    public:
    flowgraph(int v,int e){
        m_adj=new vector<flowedge *>[v+1];
        m_allEdge=new flowedge[e];
    }
    ~flowgraph(){
        delete[] m_adj;
        delete[] m_allEdge;
    }
    void add_edge(int start,int target,int value,int cost=0){
        m_allEdge[m_tail].set(start,target,value,cost);
        m_adj[start].push_back(m_allEdge+m_tail);
        m_adj[target].push_back(m_allEdge+m_tail);
        m_tail++;
    }
    vector<flowedge *> &adj(int vertex){
        return *(m_adj+vertex);
    }
};
const int N=150,M=6000;
bool marked[2*(N+1)];
flowedge* edgeTo[2*(N+1)]={};
int maxflow=0;
bool hasAugmentingPath(flowgraph &g,int s,int t){
    queue<int> q;
    q.push(s);
    memset(marked,0,sizeof(marked));
    memset(edgeTo,0,sizeof(edgeTo));
    marked[s]=true;
    while(!q.empty()){
        int current=q.front();
        q.pop();
        for(auto v:g.adj(current)){
            int w=v->other(current);
            if(!marked[w]&&v->residualCapacityTo(w)){
                edgeTo[w]=v;
                q.push(w);
                marked[w]=true;
            }
        }
    }
    return marked[t];
}
void FordFulkerson(flowgraph &g,int s,int t){
    while(hasAugmentingPath(g,s,t)){
        int delta=__INT_MAX__;
        for(int v=t;v!=s;v=edgeTo[v]->other(v)){
            if(edgeTo[v]->residualCapacityTo(v)<delta)
                delta=edgeTo[v]->residualCapacityTo(v);
        }
        for(int v=t;v!=s;v=edgeTo[v]->other(v)){
            edgeTo[v]->addResidualFlowTo(v,delta);
        }
        maxflow+=delta;
    }
}

int main() {
    int n,m,v,w;
    cin>>n>>m;
    flowgraph g(2*n+1,2*n+m);
    for(int i=1;i<=n;i++){
        g.add_edge(0,i,1);
        g.add_edge(n+i,2*n+1,1);
    }
    for(int i=0;i<m;i++){
        cin>>v>>w;
        g.add_edge(v,n+w,1);
    }
    FordFulkerson(g,0,2*n+1);
    for(int i=1;i<=n;i++){
        int v=-1;
        for(auto e:g.adj(n+i)){
            if(e->to()==2*n+1&&e->flow()==0){
                v=e->from()-n;
                break;
            }
        }
        while(v>0){
            cout<<v<<" ";
            int w=0;
            for(auto e:g.adj(v)){
                if(e->flow())
                    w=e->to()-n;
            }
            v=w;
        }
        if(v==0)
            cout<<endl;
    }
    cout<<n-maxflow<<endl;
}
